{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": true
   },
   "source": [
    "<h1>目录<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#需求\" data-toc-modified-id=\"需求-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>需求</a></span></li><li><span><a href=\"#思想\" data-toc-modified-id=\"思想-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>思想</a></span></li><li><span><a href=\"#实现\" data-toc-modified-id=\"实现-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span>实现</a></span></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 需求\n",
    "```\n",
    "给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。\n",
    "\n",
    "示例：\n",
    "\n",
    "给定一个链表: 1->2->3->4->5, 和 n = 2.\n",
    "\n",
    "当删除了倒数第二个节点后，链表变为 1->2->3->5.\n",
    "\n",
    "说明：\n",
    "\n",
    "给定的 n 保证是有效的。\n",
    "\n",
    "进阶：\n",
    "\n",
    "你能尝试使用一趟扫描实现吗？\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 思想"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. 使用3个’指针‘，fast、slow、result分别指向head\n",
    "1. fast先‘跑’n步\n",
    "1. 然后fast、slow一起‘跑’，当到达节点末尾时，此时slow指向倒数第n给位置\n",
    "1. 使用result获取第slow的指向节点，返回result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 实现\n",
    "这是leetcode的代码，在leetcode中有测试程序进行测试，我不方便模拟输入..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head, n):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type n: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "\n",
    "        fast = slow = dummy\n",
    "\n",
    "        # fast指向正向的第n个节点\n",
    "        while n and fast:\n",
    "            fast = fast.next\n",
    "            n -= 1\n",
    "        # slow处于head，此时fast领先slow n 个节点，当fast到达末尾时，此时slow指向目标节点\n",
    "        while fast.next and slow.next:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        # 获取目标节点\n",
    "        slow.next = slow.next.next"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "base"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "目录",
   "title_sidebar": "大纲",
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
